home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 58 / pcpp58a.iso / extras / quake 3 source / Q3A_ToolSource.exe / Main / polylib.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-02  |  14.0 KB  |  720 lines
  1.  
  2. #include "cmdlib.h"
  3. #include "mathlib.h"
  4. #include "polylib.h"
  5. #include "qfiles.h"
  6.  
  7.  
  8. extern int numthreads;
  9.  
  10. // counters are only bumped when running single threaded,
  11. // because they are an awefull coherence problem
  12. int    c_active_windings;
  13. int    c_peak_windings;
  14. int    c_winding_allocs;
  15. int    c_winding_points;
  16.  
  17. #define    BOGUS_RANGE    WORLD_SIZE
  18.  
  19. void pw(winding_t *w)
  20. {
  21.     int        i;
  22.     for (i=0 ; i<w->numpoints ; i++)
  23.         printf ("(%5.1f, %5.1f, %5.1f)\n",w->p[i][0], w->p[i][1],w->p[i][2]);
  24. }
  25.  
  26.  
  27. /*
  28. =============
  29. AllocWinding
  30. =============
  31. */
  32. winding_t    *AllocWinding (int points)
  33. {
  34.     winding_t    *w;
  35.     int            s;
  36.  
  37.     if (numthreads == 1)
  38.     {
  39.         c_winding_allocs++;
  40.         c_winding_points += points;
  41.         c_active_windings++;
  42.         if (c_active_windings > c_peak_windings)
  43.             c_peak_windings = c_active_windings;
  44.     }
  45.     s = sizeof(vec_t)*3*points + sizeof(int);
  46.     w = malloc (s);
  47.     memset (w, 0, s); 
  48.     return w;
  49. }
  50.  
  51. void FreeWinding (winding_t *w)
  52. {
  53.     if (*(unsigned *)w == 0xdeaddead)
  54.         Error ("FreeWinding: freed a freed winding");
  55.     *(unsigned *)w = 0xdeaddead;
  56.  
  57.     if (numthreads == 1)
  58.         c_active_windings--;
  59.     free (w);
  60. }
  61.  
  62. /*
  63. ============
  64. RemoveColinearPoints
  65. ============
  66. */
  67. int    c_removed;
  68.  
  69. void    RemoveColinearPoints (winding_t *w)
  70. {
  71.     int        i, j, k;
  72.     vec3_t    v1, v2;
  73.     int        nump;
  74.     vec3_t    p[MAX_POINTS_ON_WINDING];
  75.  
  76.     nump = 0;
  77.     for (i=0 ; i<w->numpoints ; i++)
  78.     {
  79.         j = (i+1)%w->numpoints;
  80.         k = (i+w->numpoints-1)%w->numpoints;
  81.         VectorSubtract (w->p[j], w->p[i], v1);
  82.         VectorSubtract (w->p[i], w->p[k], v2);
  83.         VectorNormalize(v1,v1);
  84.         VectorNormalize(v2,v2);
  85.         if (DotProduct(v1, v2) < 0.999)
  86.         {
  87.             VectorCopy (w->p[i], p[nump]);
  88.             nump++;
  89.         }
  90.     }
  91.  
  92.     if (nump == w->numpoints)
  93.         return;
  94.  
  95.     if (numthreads == 1)
  96.         c_removed += w->numpoints - nump;
  97.     w->numpoints = nump;
  98.     memcpy (w->p, p, nump*sizeof(p[0]));
  99. }
  100.  
  101. /*
  102. ============
  103. WindingPlane
  104. ============
  105. */
  106. void WindingPlane (winding_t *w, vec3_t normal, vec_t *dist)
  107. {
  108.     vec3_t    v1, v2;
  109.  
  110.     VectorSubtract (w->p[1], w->p[0], v1);
  111.     VectorSubtract (w->p[2], w->p[0], v2);
  112.     CrossProduct (v2, v1, normal);
  113.     VectorNormalize (normal, normal);
  114.     *dist = DotProduct (w->p[0], normal);
  115.  
  116. }
  117.  
  118. /*
  119. =============
  120. WindingArea
  121. =============
  122. */
  123. vec_t    WindingArea (winding_t *w)
  124. {
  125.     int        i;
  126.     vec3_t    d1, d2, cross;
  127.     vec_t    total;
  128.  
  129.     total = 0;
  130.     for (i=2 ; i<w->numpoints ; i++)
  131.     {
  132.         VectorSubtract (w->p[i-1], w->p[0], d1);
  133.         VectorSubtract (w->p[i], w->p[0], d2);
  134.         CrossProduct (d1, d2, cross);
  135.         total += 0.5 * VectorLength ( cross );
  136.     }
  137.     return total;
  138. }
  139.  
  140. void    WindingBounds (winding_t *w, vec3_t mins, vec3_t maxs)
  141. {
  142.     vec_t    v;
  143.     int        i,j;
  144.  
  145.     mins[0] = mins[1] = mins[2] = 99999;
  146.     maxs[0] = maxs[1] = maxs[2] = -99999;
  147.  
  148.     for (i=0 ; i<w->numpoints ; i++)
  149.     {
  150.         for (j=0 ; j<3 ; j++)
  151.         {
  152.             v = w->p[i][j];
  153.             if (v < mins[j])
  154.                 mins[j] = v;
  155.             if (v > maxs[j])
  156.                 maxs[j] = v;
  157.         }
  158.     }
  159. }
  160.  
  161. /*
  162. =============
  163. WindingCenter
  164. =============
  165. */
  166. void    WindingCenter (winding_t *w, vec3_t center)
  167. {
  168.     int        i;
  169.     float    scale;
  170.  
  171.     VectorCopy (vec3_origin, center);
  172.     for (i=0 ; i<w->numpoints ; i++)
  173.         VectorAdd (w->p[i], center, center);
  174.  
  175.     scale = 1.0/w->numpoints;
  176.     VectorScale (center, scale, center);
  177. }
  178.  
  179. /*
  180. =================
  181. BaseWindingForPlane
  182. =================
  183. */
  184. winding_t *BaseWindingForPlane (vec3_t normal, vec_t dist)
  185. {
  186.     int        i, x;
  187.     vec_t    max, v;
  188.     vec3_t    org, vright, vup;
  189.     winding_t    *w;
  190.     
  191. // find the major axis
  192.  
  193.     max = -BOGUS_RANGE;
  194.     x = -1;
  195.     for (i=0 ; i<3; i++)
  196.     {
  197.         v = fabs(normal[i]);
  198.         if (v > max)
  199.         {
  200.             x = i;
  201.             max = v;
  202.         }
  203.     }
  204.     if (x==-1)
  205.         Error ("BaseWindingForPlane: no axis found");
  206.         
  207.     VectorCopy (vec3_origin, vup);    
  208.     switch (x)
  209.     {
  210.     case 0:
  211.     case 1:
  212.         vup[2] = 1;
  213.         break;        
  214.     case 2:
  215.         vup[0] = 1;
  216.         break;        
  217.     }
  218.  
  219.     v = DotProduct (vup, normal);
  220.     VectorMA (vup, -v, normal, vup);
  221.     VectorNormalize (vup, vup);
  222.         
  223.     VectorScale (normal, dist, org);
  224.     
  225.     CrossProduct (vup, normal, vright);
  226.     
  227.     VectorScale (vup, MAX_WORLD_COORD, vup);
  228.     VectorScale (vright, MAX_WORLD_COORD, vright);
  229.  
  230. // project a really big    axis aligned box onto the plane
  231.     w = AllocWinding (4);
  232.     
  233.     VectorSubtract (org, vright, w->p[0]);
  234.     VectorAdd (w->p[0], vup, w->p[0]);
  235.     
  236.     VectorAdd (org, vright, w->p[1]);
  237.     VectorAdd (w->p[1], vup, w->p[1]);
  238.     
  239.     VectorAdd (org, vright, w->p[2]);
  240.     VectorSubtract (w->p[2], vup, w->p[2]);
  241.     
  242.     VectorSubtract (org, vright, w->p[3]);
  243.     VectorSubtract (w->p[3], vup, w->p[3]);
  244.     
  245.     w->numpoints = 4;
  246.     
  247.     return w;    
  248. }
  249.  
  250. /*
  251. ==================
  252. CopyWinding
  253. ==================
  254. */
  255. winding_t    *CopyWinding (winding_t *w)
  256. {
  257.     int            size;
  258.     winding_t    *c;
  259.  
  260.     c = AllocWinding (w->numpoints);
  261.     size = (int)((winding_t *)0)->p[w->numpoints];
  262.     memcpy (c, w, size);
  263.     return c;
  264. }
  265.  
  266. /*
  267. ==================
  268. ReverseWinding
  269. ==================
  270. */
  271. winding_t    *ReverseWinding (winding_t *w)
  272. {
  273.     int            i;
  274.     winding_t    *c;
  275.  
  276.     c = AllocWinding (w->numpoints);
  277.     for (i=0 ; i<w->numpoints ; i++)
  278.     {
  279.         VectorCopy (w->p[w->numpoints-1-i], c->p[i]);
  280.     }
  281.     c->numpoints = w->numpoints;
  282.     return c;
  283. }
  284.  
  285.  
  286. /*
  287. =============
  288. ClipWindingEpsilon
  289. =============
  290. */
  291. void    ClipWindingEpsilon (winding_t *in, vec3_t normal, vec_t dist, 
  292.                 vec_t epsilon, winding_t **front, winding_t **back)
  293. {
  294.     vec_t    dists[MAX_POINTS_ON_WINDING+4];
  295.     int        sides[MAX_POINTS_ON_WINDING+4];
  296.     int        counts[3];
  297.     static    vec_t    dot;        // VC 4.2 optimizer bug if not static
  298.     int        i, j;
  299.     vec_t    *p1, *p2;
  300.     vec3_t    mid;
  301.     winding_t    *f, *b;
  302.     int        maxpts;
  303.     
  304.     counts[0] = counts[1] = counts[2] = 0;
  305.  
  306. // determine sides for each point
  307.     for (i=0 ; i<in->numpoints ; i++)
  308.     {
  309.         dot = DotProduct (in->p[i], normal);
  310.         dot -= dist;
  311.         dists[i] = dot;
  312.         if (dot > epsilon)
  313.             sides[i] = SIDE_FRONT;
  314.         else if (dot < -epsilon)
  315.             sides[i] = SIDE_BACK;
  316.         else
  317.         {
  318.             sides[i] = SIDE_ON;
  319.         }
  320.         counts[sides[i]]++;
  321.     }
  322.     sides[i] = sides[0];
  323.     dists[i] = dists[0];
  324.     
  325.     *front = *back = NULL;
  326.  
  327.     if (!counts[0])
  328.     {
  329.         *back = CopyWinding (in);
  330.         return;
  331.     }
  332.     if (!counts[1])
  333.     {
  334.         *front = CopyWinding (in);
  335.         return;
  336.     }
  337.  
  338.     maxpts = in->numpoints+4;    // cant use counts[0]+2 because
  339.                                 // of fp grouping errors
  340.  
  341.     *front = f = AllocWinding (maxpts);
  342.     *back = b = AllocWinding (maxpts);
  343.         
  344.     for (i=0 ; i<in->numpoints ; i++)
  345.     {
  346.         p1 = in->p[i];
  347.         
  348.         if (sides[i] == SIDE_ON)
  349.         {
  350.             VectorCopy (p1, f->p[f->numpoints]);
  351.             f->numpoints++;
  352.             VectorCopy (p1, b->p[b->numpoints]);
  353.             b->numpoints++;
  354.             continue;
  355.         }
  356.     
  357.         if (sides[i] == SIDE_FRONT)
  358.         {
  359.             VectorCopy (p1, f->p[f->numpoints]);
  360.             f->numpoints++;
  361.         }
  362.         if (sides[i] == SIDE_BACK)
  363.         {
  364.             VectorCopy (p1, b->p[b->numpoints]);
  365.             b->numpoints++;
  366.         }
  367.  
  368.         if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
  369.             continue;
  370.             
  371.     // generate a split point
  372.         p2 = in->p[(i+1)%in->numpoints];
  373.         
  374.         dot = dists[i] / (dists[i]-dists[i+1]);
  375.         for (j=0 ; j<3 ; j++)
  376.         {    // avoid round off error when possible
  377.             if (normal[j] == 1)
  378.                 mid[j] = dist;
  379.             else if (normal[j] == -1)
  380.                 mid[j] = -dist;
  381.             else
  382.                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
  383.         }
  384.             
  385.         VectorCopy (mid, f->p[f->numpoints]);
  386.         f->numpoints++;
  387.         VectorCopy (mid, b->p[b->numpoints]);
  388.         b->numpoints++;
  389.     }
  390.     
  391.     if (f->numpoints > maxpts || b->numpoints > maxpts)
  392.         Error ("ClipWinding: points exceeded estimate");
  393.     if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
  394.         Error ("ClipWinding: MAX_POINTS_ON_WINDING");
  395. }
  396.  
  397.  
  398. /*
  399. =============
  400. ChopWindingInPlace
  401. =============
  402. */
  403. void ChopWindingInPlace (winding_t **inout, vec3_t normal, vec_t dist, vec_t epsilon)
  404. {
  405.     winding_t    *in;
  406.     vec_t    dists[MAX_POINTS_ON_WINDING+4];
  407.     int        sides[MAX_POINTS_ON_WINDING+4];
  408.     int        counts[3];
  409.     static    vec_t    dot;        // VC 4.2 optimizer bug if not static
  410.     int        i, j;
  411.     vec_t    *p1, *p2;
  412.     vec3_t    mid;
  413.     winding_t    *f;
  414.     int        maxpts;
  415.  
  416.     in = *inout;
  417.     counts[0] = counts[1] = counts[2] = 0;
  418.  
  419. // determine sides for each point
  420.     for (i=0 ; i<in->numpoints ; i++)
  421.     {
  422.         dot = DotProduct (in->p[i], normal);
  423.         dot -= dist;
  424.         dists[i] = dot;
  425.         if (dot > epsilon)
  426.             sides[i] = SIDE_FRONT;
  427.         else if (dot < -epsilon)
  428.             sides[i] = SIDE_BACK;
  429.         else
  430.         {
  431.             sides[i] = SIDE_ON;
  432.         }
  433.         counts[sides[i]]++;
  434.     }
  435.     sides[i] = sides[0];
  436.     dists[i] = dists[0];
  437.     
  438.     if (!counts[0])
  439.     {
  440.         FreeWinding (in);
  441.         *inout = NULL;
  442.         return;
  443.     }
  444.     if (!counts[1])
  445.         return;        // inout stays the same
  446.  
  447.     maxpts = in->numpoints+4;    // cant use counts[0]+2 because
  448.                                 // of fp grouping errors
  449.  
  450.     f = AllocWinding (maxpts);
  451.         
  452.     for (i=0 ; i<in->numpoints ; i++)
  453.     {
  454.         p1 = in->p[i];
  455.         
  456.         if (sides[i] == SIDE_ON)
  457.         {
  458.             VectorCopy (p1, f->p[f->numpoints]);
  459.             f->numpoints++;
  460.             continue;
  461.         }
  462.     
  463.         if (sides[i] == SIDE_FRONT)
  464.         {
  465.             VectorCopy (p1, f->p[f->numpoints]);
  466.             f->numpoints++;
  467.         }
  468.  
  469.         if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
  470.             continue;
  471.             
  472.     // generate a split point
  473.         p2 = in->p[(i+1)%in->numpoints];
  474.         
  475.         dot = dists[i] / (dists[i]-dists[i+1]);
  476.         for (j=0 ; j<3 ; j++)
  477.         {    // avoid round off error when possible
  478.             if (normal[j] == 1)
  479.                 mid[j] = dist;
  480.             else if (normal[j] == -1)
  481.                 mid[j] = -dist;
  482.             else
  483.                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
  484.         }
  485.             
  486.         VectorCopy (mid, f->p[f->numpoints]);
  487.         f->numpoints++;
  488.     }
  489.     
  490.     if (f->numpoints > maxpts)
  491.         Error ("ClipWinding: points exceeded estimate");
  492.     if (f->numpoints > MAX_POINTS_ON_WINDING)
  493.         Error ("ClipWinding: MAX_POINTS_ON_WINDING");
  494.  
  495.     FreeWinding (in);
  496.     *inout = f;
  497. }
  498.  
  499.  
  500. /*
  501. =================
  502. ChopWinding
  503.  
  504. Returns the fragment of in that is on the front side
  505. of the cliping plane.  The original is freed.
  506. =================
  507. */
  508. winding_t    *ChopWinding (winding_t *in, vec3_t normal, vec_t dist)
  509. {
  510.     winding_t    *f, *b;
  511.  
  512.     ClipWindingEpsilon (in, normal, dist, ON_EPSILON, &f, &b);
  513.     FreeWinding (in);
  514.     if (b)
  515.         FreeWinding (b);
  516.     return f;
  517. }
  518.  
  519.  
  520. /*
  521. =================
  522. CheckWinding
  523.  
  524. =================
  525. */
  526. void CheckWinding (winding_t *w)
  527. {
  528.     int        i, j;
  529.     vec_t    *p1, *p2;
  530.     vec_t    d, edgedist;
  531.     vec3_t    dir, edgenormal, facenormal;
  532.     vec_t    area;
  533.     vec_t    facedist;
  534.  
  535.     if (w->numpoints < 3)
  536.         Error ("CheckWinding: %i points",w->numpoints);
  537.     
  538.     area = WindingArea(w);
  539.     if (area < 1)
  540.         Error ("CheckWinding: %f area", area);
  541.  
  542.     WindingPlane (w, facenormal, &facedist);
  543.     
  544.     for (i=0 ; i<w->numpoints ; i++)
  545.     {
  546.         p1 = w->p[i];
  547.  
  548.         for (j=0 ; j<3 ; j++)
  549.             if (p1[j] > MAX_WORLD_COORD || p1[j] < MIN_WORLD_COORD)
  550.                 Error ("CheckFace: BUGUS_RANGE: %f",p1[j]);
  551.  
  552.         j = i+1 == w->numpoints ? 0 : i+1;
  553.         
  554.     // check the point is on the face plane
  555.         d = DotProduct (p1, facenormal) - facedist;
  556.         if (d < -ON_EPSILON || d > ON_EPSILON)
  557.             Error ("CheckWinding: point off plane");
  558.     
  559.     // check the edge isnt degenerate
  560.         p2 = w->p[j];
  561.         VectorSubtract (p2, p1, dir);
  562.         
  563.         if (VectorLength (dir) < ON_EPSILON)
  564.             Error ("CheckWinding: degenerate edge");
  565.             
  566.         CrossProduct (facenormal, dir, edgenormal);
  567.         VectorNormalize (edgenormal, edgenormal);
  568.         edgedist = DotProduct (p1, edgenormal);
  569.         edgedist += ON_EPSILON;
  570.         
  571.     // all other points must be on front side
  572.         for (j=0 ; j<w->numpoints ; j++)
  573.         {
  574.             if (j == i)
  575.                 continue;
  576.             d = DotProduct (w->p[j], edgenormal);
  577.             if (d > edgedist)
  578.                 Error ("CheckWinding: non-convex");
  579.         }
  580.     }
  581. }
  582.  
  583.  
  584. /*
  585. ============
  586. WindingOnPlaneSide
  587. ============
  588. */
  589. int        WindingOnPlaneSide (winding_t *w, vec3_t normal, vec_t dist)
  590. {
  591.     qboolean    front, back;
  592.     int            i;
  593.     vec_t        d;
  594.  
  595.     front = qfalse;
  596.     back = qfalse;
  597.     for (i=0 ; i<w->numpoints ; i++)
  598.     {
  599.         d = DotProduct (w->p[i], normal) - dist;
  600.         if (d < -ON_EPSILON)
  601.         {
  602.             if (front)
  603.                 return SIDE_CROSS;
  604.             back = qtrue;
  605.             continue;
  606.         }
  607.         if (d > ON_EPSILON)
  608.         {
  609.             if (back)
  610.                 return SIDE_CROSS;
  611.             front = qtrue;
  612.             continue;
  613.         }
  614.     }
  615.  
  616.     if (back)
  617.         return SIDE_BACK;
  618.     if (front)
  619.         return SIDE_FRONT;
  620.     return SIDE_ON;
  621. }
  622.  
  623.  
  624. /*
  625. =================
  626. AddWindingToConvexHull
  627.  
  628. Both w and *hull are on the same plane
  629. =================
  630. */
  631. #define    MAX_HULL_POINTS        128
  632. void    AddWindingToConvexHull( winding_t *w, winding_t **hull, vec3_t normal ) {
  633.     int            i, j, k;
  634.     float        *p, *copy;
  635.     vec3_t        dir;
  636.     float        d;
  637.     int            numHullPoints, numNew;
  638.     vec3_t        hullPoints[MAX_HULL_POINTS];
  639.     vec3_t        newHullPoints[MAX_HULL_POINTS];
  640.     vec3_t        hullDirs[MAX_HULL_POINTS];
  641.     qboolean    hullSide[MAX_HULL_POINTS];
  642.     qboolean    outside;
  643.  
  644.     if ( !*hull ) {
  645.         *hull = CopyWinding( w );
  646.         return;
  647.     }
  648.  
  649.     numHullPoints = (*hull)->numpoints;
  650.     memcpy( hullPoints, (*hull)->p, numHullPoints * sizeof(vec3_t) );
  651.  
  652.     for ( i = 0 ; i < w->numpoints ; i++ ) {
  653.         p = w->p[i];
  654.  
  655.         // calculate hull side vectors
  656.         for ( j = 0 ; j < numHullPoints ; j++ ) {
  657.             k = ( j + 1 ) % numHullPoints;
  658.  
  659.             VectorSubtract( hullPoints[k], hullPoints[j], dir );
  660.             VectorNormalize( dir, dir );
  661.             CrossProduct( normal, dir, hullDirs[j] );
  662.         }
  663.  
  664.         outside = qfalse;
  665.         for ( j = 0 ; j < numHullPoints ; j++ ) {
  666.             VectorSubtract( p, hullPoints[j], dir );
  667.             d = DotProduct( dir, hullDirs[j] );
  668.             if ( d >= ON_EPSILON ) {
  669.                 outside = qtrue;
  670.             }
  671.             if ( d >= -ON_EPSILON ) {
  672.                 hullSide[j] = qtrue;
  673.             } else {
  674.                 hullSide[j] = qfalse;
  675.             }
  676.         }
  677.  
  678.         // if the point is effectively inside, do nothing
  679.         if ( !outside ) {
  680.             continue;
  681.         }
  682.  
  683.         // find the back side to front side transition
  684.         for ( j = 0 ; j < numHullPoints ; j++ ) {
  685.             if ( !hullSide[ j % numHullPoints ] && hullSide[ (j + 1) % numHullPoints ] ) {
  686.                 break;
  687.             }
  688.         }
  689.         if ( j == numHullPoints ) {
  690.             continue;
  691.         }
  692.  
  693.         // insert the point here
  694.         VectorCopy( p, newHullPoints[0] );
  695.         numNew = 1;
  696.  
  697.         // copy over all points that aren't double fronts
  698.         j = (j+1)%numHullPoints;
  699.         for ( k = 0 ; k < numHullPoints ; k++ ) {
  700.             if ( hullSide[ (j+k) % numHullPoints ] && hullSide[ (j+k+1) % numHullPoints ] ) {
  701.                 continue;
  702.             }
  703.             copy = hullPoints[ (j+k+1) % numHullPoints ];
  704.             VectorCopy( copy, newHullPoints[numNew] );
  705.             numNew++;
  706.         }
  707.  
  708.         numHullPoints = numNew;
  709.         memcpy( hullPoints, newHullPoints, numHullPoints * sizeof(vec3_t) );
  710.     }
  711.  
  712.     FreeWinding( *hull );
  713.     w = AllocWinding( numHullPoints );
  714.     w->numpoints = numHullPoints;
  715.     *hull = w;
  716.     memcpy( w->p, hullPoints, numHullPoints * sizeof(vec3_t) );
  717. }
  718.  
  719.  
  720.